The present invention relates to signal processing using time compressors, fast Fourier transformers, and more particularly to digital signal processing in which signals are represented by a series of coded digits, for example digits found at the output of an analog-to-digital converter.
The linear and bilinear operations most needed for signal processing are: matched filtering, cross correlation, and the discrete Fourier transform (DFT). These transforms represent an excessive computational load for a general purpose computer and a heavy load even for a digital computer structured for signal processing. For example, a straightforward linear transformation in a computer that takes a sequence of N data points into a sequence of N transform points may be regarded as a multiplication by a vector N.sup.2 matrix. A direct implementation of the DFT, as example, requires N.sup.2 multiplication times and N.sup.2 words of storage. The fast Fourier transform (FFT) obtains the same result with Nlog.sub.2 N multiplications and Nlog.sub.2 N words of storage. This can all be seen in a number of publications including the book by Gold and Rader "Digital Processing of Signals" McGraw-Hill 1969 and in the book edited by Rabiner Rader "Digital Signal Processing" IEEE Press. 1972 and in the paper by Bergland, "A Fast Fourier Transform Algorithm for Real-Valued Series," appearing in the October, 1968 issue of Communication of the ACM.
In the present art the computation of the DFT via the FFT in a general purpose computer having an execution time of 1 millisecond/operation is Nlog.sub.2 N milliseconds and this becomes quite large even for modest values of N. Cascading, paralleling, and arraying computers quickly increases the cost. As a consequence, while the general purpose computer has the potential for computing the DFT it falls short in many applications which require real time operation. Special purpose hardware on the other hand is known in the present art having execution times on the order of 1 microsecond/operation and these are indicated for many applications where the DFT processing must be accomplished in real time. FFT hardware has been discussed in the article by Bergland "FFT Transform Hardware Implementations -- An Overview" appearing in the June, 1969 issue of IEEE Transactions on Audio and Electro-acoustics, and in the article by Groginsky and Works "A Pipeline Fast Fourier Transform" appearing in the November, 1970 issue of IEEE Transactions on Computers. FFT processors may be implemented using any one of a number of technologies and these have been discussed in a number of publications including the paper by Whitehouse et al. "High Speed Serial Access Linear Transform Implementations" Naval Undersea Center, San Diego, CA 92132 January, 1973. In general, apparatus fall into two broad categories; those employing acoustic means and non-acoustic means. Included in the former category are sonic, magneto-strictive, acoustic surface wave, and opto-acoustic filters, while the latter category comprises charge coupled devices (CCD), and binary shift registers (BSR). Acoustic filters have been described in the paper by Squire et al. "Linear Signal Processing and Ultrasonic Transversal Filters" appearing in the November, 1969 issue of IEEE Transactions on Microwave Theory and Techniques, and in the paper by Holland and Claiborne "Practical Acoustic Wave Devices" appearing in the May, 1974 issue of IEEE Proceedings, while non-acoustic filters have been described in the paper by Byram et al. "Signal Processing Device Technology" appearing in the Proceedings of the NATO Advanced Study Institute on Signal Processing held at the University of Technology, Loughborough, U. K. on Aug. 21 through Sept. 1, 1972, and in the papers by Kosnocky, and Buss et al. appearing in Tecnical Session 2 "Introduction to Charge Coupled Devices" 1974 WESCON, Los Angles, Sept. 10 through 13, 1974.
As a rule, if interruptions of the processing are infrequent then acoustic filters are preferred since they offer large storage capacity, convenient tapping of delay lines, and lower power dissipation. When short-duration interruptions of the signal processing may occur then CCD with their controllable clock rates offer the advantages of small size, offset only by charge transfer inefficiency and temperature sensitivity. When frequent processing interrupts are required then digital implementations in the form of shift registers are indicated. The rapid development however of solid state technology favors digital devices and these by far have now become the preferred devices for implementing signal processors.
Digital implementations of the present art have been obtained in the form of shift registers, BSR, CCD and so forth. Such devices can be assembled from conventional medium scale integrated (MSI) circuit logic or can be designed in large scale integrated (LSI) form. Thus, the digital implementation of a FFT processor requires the high speed storage and readout of data in a number of shift registers. However, shift registers are limited in length and speed, and many similar devices are needed if much data is to be stored. Metal-oxide (MOS) registers while providing high density are slow speed when used as bipolar shift registers.
In many signal processing applications the signals must be compressed in time. This is accomplished in the prior art by storing signals in a delay line and then retrieving them at a rate which is greater than the rate of storage, as explained in the article by Squire. Of particular interest is the delay time compressor (DELTIC) which recirculates in a number of recirculations. The recirculation requires less length of delay line and therefore is a more efficient system. The DELTIC circuit has been used for implementing digital time compressors, matched filters, and correlators and this can be seen in my copending applications Ser. Nos. 450,606 filed Mar. 13, 1974 and 479,872 filed June 17, 1974.
In general, the prior digital art using shift registers utilize 3N/2 words of storage and N multipliers at a given section in the computation of the DFT via the FFT. While the system of the present invention may also utilize 3N/2 words of storage per section its implementation using RAM and a digital DELTIC loop requires but a single multiplier per section and in this manner provides new and improved FFT processors while sugnificantly decreasing the weight, size, power consumption, and cost for such devices.
From the discussion above it is clear that in the past, the digital implementation of a FFT processor using special purpose hardware has been accomplished utilizing shift registers in the memory elements and, for all practical purposes, has not been successful for inceasing the capacity and speed of operation of such devices beyond a certain limit determined by the technology of shift registers. Furthermore, the present art of digital implementations falls short when the size and cost of shift registers are considered in devices requiring high throughputs.
It is the purpose of the present invention to produce a FFT processor capable of exceeding the practical capacity and speed of present digital devices by at least one order of magnitude, at reduced size and cost.